#include <vector>
#include <iostream>
#include <cstdlib>

using namespace std;

class Solution {
  private:
    int *aux;
    vector<int> result;

    void merge(vector<int> &numbers, int low, int pivot, int high) {
      for (int i = low; i <= high; ++i) {
        aux[i] = numbers[i];
      }

      int j = low, k = pivot + 1;
      for (int i = low; i <= high; ++i) {
        if (j > pivot) {
          numbers[i] = aux[k++];
        } else if (k > high) {
          numbers[i] = aux[j++];
        } else if (aux[j] < aux[k]) {
          numbers[i] = aux[j++];
        } else {
          numbers[i] = aux[k++];
        }
      }
    }

    void _sort(vector<int> &numbers, int low, int high) {
      if (low >= high) return;

      int pivot = (low + high) / 2;

      _sort(numbers, low, pivot);
      _sort(numbers, pivot + 1, high);
      merge(numbers, low, pivot, high);
    }

    void sort(vector<int> &numbers, int N) {
      aux = (int *)calloc(N, sizeof(int));
      _sort(numbers, 0, N - 1);
    }

    void exch(int &i, int &j) {
      int temp = i;
      i = j;
      j = temp;
    }

  public:
    vector<int> twoSum(vector<int> &numbers, int target) {
      int size = (int)numbers.size();
      vector<int> sortedNumbers(numbers);
      sort(sortedNumbers, size);

      int i = 0, j = size - 1;

      while (i < j) {
        int sum = sortedNumbers[i] + sortedNumbers[j];
        if (sum == target) {
          if (i > j) exch(i, j);
          result.push_back(i + 1);
          result.push_back(j + 1);
          return result;
        } else if (sum < target) {
          ++i;
        } else {
          --j;
        }
      }
    }
};

int main()
{
  vector<int> numbers;
  numbers.push_back(3);
  numbers.push_back(2);
  numbers.push_back(4);

  Solution solution;

  vector<int> result = solution.twoSum(numbers, 6);

  cout<<"first: "<<result[0]<<"\tsecond: "<<result[1]<<endl;

  return 0;
}
